package cn.xiaolang.function.data_structure;

/**
 * 给定一个32位整数 num，你可以将一个数位从0变为1。请编写一个程序，找出你能够获得的最长的一串1的长度。
 * <p>
 * 示例 1：
 * 输入: num = 1775(11011101111)
 * 输出: 8
 * <p>
 * 示例 2：
 * 输入: num = 7(0111)
 * 输出: 4
 */
public class No12revertBits {

    public static void main(String[] args) {
        System.out.println(reverseBitsMine(-1));
    }

    /**
     * 11011101111
     * - num & 1 判断最右边1bit是0还是1
     * - num >> 1 右移1bit循环下一bit
     * current: 连续位数1的统计，遇0重新统计
     * reverse: 阶段最大连续反转位数，遇0重置为该阶段最大；（滚动）
     * max: 最大连续反转位数
     * 1. 如果是1，current++, reverse++
     * 2. 如果是0，current重置，reverse置为阶段最大反转
     */
    public static int reverseBits(int num) {
        // 最大反转位数
        int max = 0;
        int reverse = 0;
        int current = 0;

        for (int i = 0; i < 32; i++) {
            if ((num & 1) == 1) {
                // 为1
                current++;
                reverse++;
            } else {
                // 为0
                reverse = current + 1;
                current = 0;
            }
            max = Math.max(reverse, max);
            num = num >> 1;
        }
        return max;
    }

    /*
        执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
        内存消耗：37.9 MB, 在所有 Java 提交中击败了94.84%的用户
     */
    public static int reverseBitsMine(int num) {
        // 最大反转位数
        int max = 0;
        int reverse = 0;
        int current = 0;

        String bitStr = Integer.toBinaryString(num);

        for (int i = 0; i < bitStr.length(); i++) {
            if (bitStr.charAt(i) == '1') {
                // 为1
                current++;
                reverse++;
                // 处理边界：Integer.MAX_VALUE 以及最大位数
                if (reverse == bitStr.length() && reverse < 32) {
                    return reverse + 1;
                }
            } else {
                // 为0
                reverse = current + 1;
                current = 0;
            }
            max = Math.max(reverse, max);
            num = num >> 1;
        }
        return max;
    }
}
